

public class BinaryTree {
    public static class BTNode {
        BTNode left;
        BTNode right;
        int value;

        BTNode(int value) {
            this.value = value;
        }
    }

    public BTNode root;

    public BTNode createBinaryTree() {
        BTNode node1 = new BTNode(1);
        BTNode node2 = new BTNode(2);
        BTNode node3 = new BTNode(3);
        BTNode node4 = new BTNode(4);
        BTNode node5 = new BTNode(5);
        BTNode node6 = new BTNode(6);
        root = node1;
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node5.right = node6;
        return root;
    }

    public int size(BTNode root) {
        if (root == null) {
            return 0;
        }
        int leftSize = size(root.left);
        int rightSize = size(root.right);
        return leftSize + rightSize + 1;
    }

    int getLeafNodeCount(BTNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int leftSize = getLeafNodeCount(root.left);
        int rightSize = getLeafNodeCount(root.right);
        return leftSize + rightSize;
    }

    public int maxDepth(BTNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);

        return (leftHeight > rightHeight) ?
                (leftHeight + 1) : (rightHeight + 1);
    }

    BTNode find(BTNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.value == val) {
            return root;
        }
        BTNode leftTree = find(root.left, val);
        if (leftTree != null) {
            return leftTree;
        }
        BTNode rightTree = find(root.right, val);
        if (rightTree != null) {
            return rightTree;
        }
        return null;//没有找到
    }
}